Existing computer programs known as road-mapping programs provide digital maps, often complete with detailed road networks down to the city-street level. Typically, a user can input a location and the road-mapping program will display an on-screen map of the selected location. Some road-mapping products include the ability to calculate a best route between two locations. The user can input two locations, and the road-mapping program will compute the driving directions from the source location to the destination location.
The computation of driving directions can be modeled as finding the shortest path on a graph which may represent a road map or network. Given a source (the origin) and a target (the destination), the goal is to find the shortest (least costly) path from the source to the target. Existing road-mapping programs employ variants of a method attributed to Dijkstra to compute shortest paths. Dijkstra's algorithm, which is well known, is the standard solution to this problem. It processes vertices one by one, in order of increasing distance from the source, until the destination is reached.
Thus, motivated by web-based map services and autonomous navigation systems, the problem of finding shortest paths in road maps and networks has received a great deal of attention recently. However, research has focused on accelerating point-to-point queries, in which both a source and a target are known, as opposed to the single-source shortest path problem which is another well known optimization problem.
For the single-source shortest path problem, given a graph G containing a set of vertices V (the number of vertices is denoted by n) in a collection of data A (i.e., G=(V, A)), a length l(a) assigned to each arc a εA, and a source vertex, the goal is to find shortest paths from the source vertex to all other vertices in the graph. The non-negative single-source shortest path (NSSP) problem, in which l(a)≧0, is a special case that comes up in many applications. It can be solved using Dijkstra's algorithm. However, Dijkstra's algorithm is not sufficiently fast for some applications, for example those that require many shortest path trees to be computed, like all pairs of shortest paths on the road network of Europe or North America.